#ifndef GRAPH_H
#define GRAPH_H

#include <stdlib.h>
#include <iostream>
#include <fstream>
#include "List.h"
#include "Stack.h"
#include "Queue.h"

using namespace std;

const double MAXCOST = 1000000; //最大权

struct PathData //用于最小生成树、单元最短路径等算法的结构
{
    int start, dest; //边的起点和终点的下标
    double cost;     //边上的权代表费用
    operator double() const
    {
        return cost; //成员转换函数，用于比较运算
    }
};

template <class T>
class Graph
{
    struct EdgeNode //边结点数据结构
    {
        int dest;    //边的终点下标
        double cost; //边的权
        operator int()
        {
            return dest; //成员转换函数
        }
    };

private:
    T *VA;                                                     //顶点数组指针
    List<EdgeNode> *HL;                                        //边链表数组指针
    int sizeV, sizeE;                                          //顶点数，边数
    int maxV;                                                  //顶点数组空间长度
    int InDegree(int pos) const;                               //读取下标为pos的顶点入度
    double GetCost(int si, int dj) const;                      //按始点和终点下标读取边的权
    void PercolateDown(PathData E[], int pos, int size) const; //从下标pos开始，向下调整为堆
    void BuildHeap(PathData E[], int size) const;              //建堆
    void BFS(List<T> &L, int pos, bool visited[]) const;
    void DFS(List<T> &L, int pos, bool visited[]) const;

public:
    Graph(int n = 100) : sizeV(0), sizeE(0), maxV(n) //构造函数
    {
        VA = new T[n];
        HL = new List<EdgeNode>[n];
    }
    ~Graph()
    {
        delete[] VA; //析构函数
        delete[] HL;
    }
    int Empty() const
    {
        return sizeV == 0; //判空
    }
    int Full() const
    {
        return sizeV == maxV; //判满
    }
    int SizeV() const
    {
        return sizeV; //取顶点数
    }
    int SizeE() const
    {
        return sizeE; //取边数
    }
    double GetCost(const T &v1, const T &v2) const; //取权
    int FindNode(const T &v) const;                 //取顶点的下标
    bool FindNode(T &v, int pos) const;             //将下标为pos的顶点存储到v中

    bool InsertV(const T &v);                         //插入顶点
    bool InsertE(const T &v1, const T &v2, double w); //插入边
    bool DeleteV(const T &v);                         //删除顶点
    bool DeleteE(const T &v1, const T &v2);           //删除边

    void BFS(List<T> &L, const T &v) const; //广度优先遍历一个连同子图
    void BFS(List<T> &L) const;
    void DFS(List<T> &L, const T &v) const;
    void DFS(List<T> &L) const;

    void ReadGraph(const char *filename);  //从文件读取图的数据
    void WriteGraph(const char *filename); //把图的数据写（输出）到文件
    template <typename T1>
    friend ostream &operator<<(ostream &ostr, const Graph<T1> &g); //重载输出运算符
    template <typename T1>
    friend istream &operator>>(istream &istr, Graph<T1> &g); //重载输入运算符

    bool Prim(const T &v, PathData E[], int ne) const;           //普里姆算法（ne表示最小生成树中边的个数，应该是结点顶点个数减1）
    bool Kruskal(PathData E[], int nv) const;                    //克鲁斯卡尔算法
    bool Dijkstra(const T &v, double D[], int P[], int n) const; //单源最短路径
    double MinPath(const T &sv, const T &ev) const;              //两个顶点间的最短路径成本
    void AllPath(double *A[], int *P[], int nv) const;
    bool TopSort(int *t, int n) const;                        //
    bool TopSort(List<T> &L) const;                           //拓扑序列
    void CriticalPath(double VE[], double VL[], int n) const; //关键路径
};

template <class T> //把长度为size的PathData结构数组调整为堆
void Graph<T>::BuildHeap(PathData E[], int size) const
{
    for (int i = size / 2 - 1; i >= 0; i--) //从临近叶子的第一个非叶子结点至根结点扫描
        PercolateDown(E, i, size);          //把下标[i,size)之间的元素向下调整为堆
}
template <class T> //将下标[pos,size)范围内的PathData结构数组元素向下调整为堆
void Graph<T>::PercolateDown(PathData E[], int pos, int size) const
{
    int p = pos, c = 2 * p + 1;
    PathData temp = E[p];
    while (c < size)
    {
        if (c + 1 < size && E[c + 1] < E[c]) //隐式调用PathData成员转换函数来比较权
            ++c;
        if (temp < E[c])
            break;
        else
        {
            E[p] = E[c];
            p = c;
            c = 2 * p + 1;
        }
    }
    E[p] = temp;
}

template <class T>
int Graph<T>::InDegree(int pos) const
{
    int id = 0;
    for (int i = 0; i < sizeV; i++)
    {
        typename List<EdgeNode>::const_iterator first = HL[i].begin(), last = HL[i].end();
        for (; first != last; ++first)
            if ((*first).dest == pos)
            {
                id++;
                break;
            }
    }
    return id;
}
template <class T>
double Graph<T>::GetCost(int si, int dj) const
{
    if (si < 0 || si >= sizeV || dj < 0 || dj >= sizeV || si == dj)
        return (0);
    typename List<EdgeNode>::const_iterator first = HL[si].begin(), last = HL[si].end();
    for (; first != last; ++first)
        if ((*first).dest == dj)
            return (*first).cost;
    return 0;
}
template <class T>
int Graph<T>::FindNode(const T &v) const
{
    for (int i = 0; i < sizeV; i++)
        if (VA[i] == v)
            return i;
    return -1;
}
template <class T>
bool Graph<T>::FindNode(T &v, int pos) const
{
    if (pos < 0 || pos >= sizeV)
        return 0;
    v = VA[pos];
    return 1;
}
template <class T>
double Graph<T>::GetCost(const T &v1, const T &v2) const
{
    return GetCost(FindNode(v1), FindNode(v2));
}

template <class T>
bool Graph<T>::InsertV(const T &v)
{
    if (sizeV == maxV)
        return 0;
    VA[sizeV] = v;
    sizeV++;
    return 1;
}
template <class T>
bool Graph<T>::InsertE(const T &v1, const T &v2, double w)
{
    int si = FindNode(v1), dj = FindNode(v2);
    if (si == -1 || dj == -1 || si == dj)
        return (0);
    EdgeNode en;
    en.dest = dj;
    en.cost = w;
    HL[si].Insert(HL[si].end(), en);
    sizeE++;
    return 1;
}

template <class T>
bool Graph<T>::DeleteV(const T &v)
{
    int si = FindNode(v);
    if (si == -1)
        return (0);
    int temp = HL[si].Size();
    for (int i = si; i < sizeV - 1; i++)
    {
        VA[i] = VA[i + 1];
        HL[i] = HL[i + 1];
    }
    HL[sizeV - 1].Clear();
    sizeV--;
    sizeE = sizeE - temp;
    int i;
    typename List<EdgeNode>::iterator first, last;
    for (i = 0; i < sizeV; i++)
    {
        first = HL[i].begin(), last = HL[i].end();
        for (; first != last; ++first)
            if ((*first).dest == si)
            {
                HL[i].Erase(first);
                sizeE--;
                break;
            }
    }
    for (i = 0; i < sizeV; i++)
    {
        first = HL[i].begin(), last = HL[i].end();
        for (; first != last; ++first)
            if ((*first).dest > si)
                (*first).dest--;
    }
    return 1;
}
template <class T>
bool Graph<T>::DeleteE(const T &v1, const T &v2)
{
    int si = FindNode(v1), dj = FindNode(v2);
    if (si == -1 || dj == -1 || si == dj)
        return (0);
    typename List<EdgeNode>::iterator first = HL[si].begin(), last = HL[si].end();
    for (; first != last; ++first)
        if ((*first).dest == dj)
        {
            HL[si].Erase(first);
            sizeE--;
            return 1;
        }
    return 0;
}
template <class T>
void Graph<T>::ReadGraph(const char *filename)
{
    char str[50];
    int n;
    double w;
    T v1, v2;
    ifstream fin;
    fin.open(filename, ios::in); //此处删去ios::nocreatefin.open(filename, ios::in | ios::nocreate);
    if (!fin)
    {
        cout << "cannot open " << filename << endl;
        exit(1);
    }
    fin >> str >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> v1;
        InsertV(v1);
    }
    fin >> str >> n;
    int i;
    for (i = 1; i <= n; ++i)
    {
        fin >> v1 >> v2 >> w;
        InsertE(v1, v2, w);
    }
}
template <class T>
void Graph<T>::WriteGraph(const char *filename)
{
    ofstream fout;
    fout.open(filename, ios::out);
    if (!fout)
    {
        cout << "cannot open " << filename << endl;
        exit(1);
    }
    for (int i = 0; i < sizeV; i++)
    {
        fout << i << '-' << VA[i] << ':';
        typename List<Graph<T>::EdgeNode>::iterator first = HL[i].begin(), last = HL[i].end();
        for (; first != last; ++first)
            fout << '(' << (*first).dest << ',' << (*first).cost << ')' << ' ';
        fout << endl;
    }
}
template <class T>
istream &operator>>(istream &istr, Graph<T> &g)
{
    char str[50];
    int n;
    double w;
    T v1, v2;
    istr >> str >> n;
    for (int i = 1; i <= n; ++i)
    {
        istr >> v1;
        g.InsertV(v1);
    }
    istr >> str >> n;
    int i;
    for (i = 1; i <= n; ++i)
    {
        istr >> v1 >> v2 >> w;
        g.InsertE(v1, v2, w);
    }
    return istr;
}

template <class T>
ostream &operator<<(ostream &ostr, const Graph<T> &g)
{
    for (int i = 0; i < g.sizeV; i++)
    {
        ostr << i << '-' << g.VA[i] << ':';
        typename List<typename Graph<T>::EdgeNode>::iterator first = g.HL[i].begin(), last = g.HL[i].end();
        for (; first != last; ++first)
            ostr << '(' << (*first).dest << ',' << (*first).cost << ')' << ' ';
        ostr << endl;
    }
    return ostr;
}
template <class T>
void Graph<T>::BFS(List<T> &L, int pos, bool visited[]) const
{
    if (pos < 0 || pos >= sizeV)
        return;
    Queue<int> Q;
    Q.Push(pos);
    visited[pos] = 1;
    typename List<EdgeNode>::const_iterator first, last;
    while (!Q.Empty())
    {
        pos = Q.Pop();
        L.Push_back(VA[pos]);
        first = HL[pos].begin();
        last = HL[pos].end();
        for (; first != last; ++first)
            if (visited[(*first).dest] == 0)
            {
                Q.Push((*first).dest);
                visited[(*first).dest] = 1;
            }
    }
}
template <class T>
void Graph<T>::BFS(List<T> &L) const
{
    bool *visited = new bool[sizeV];
    for (int i = 0; i < sizeV; i++)
        visited[i] = 0;
    int i;
    for (i = 0; i < sizeV; i++)
        if (visited[i] == 0)
            BFS(L, i, visited);
}

template <class T>
void Graph<T>::BFS(List<T> &L, const T &v) const
{
    int pos = FindNode(v), i;
    if (pos == -1)
        return;
    bool *visited = new bool[sizeV];
    for (i = 0; i < sizeV; i++)
        visited[i] = 0;
    Queue<int> Q;
    Q.Push(pos);
    visited[pos] = 1;
    typename List<EdgeNode>::const_iterator first, last;
    while (!Q.Empty())
    {
        pos = Q.Pop();
        L.Push_back(VA[pos]);
        first = HL[pos].begin();
        last = HL[pos].end();
        for (; first != last; ++first)
            if (visited[(*first).dest] == 0)
            {
                Q.Push((*first).dest);
                visited[(*first).dest] = 1;
            }
    }
}

template <class T>
void Graph<T>::DFS(List<T> &L, int pos, bool visited[]) const
{
    if (pos < 0 || pos >= sizeV)
        return;
    L.Push_back(VA[pos]);
    visited[pos] = 1;
    typename List<EdgeNode>::const_iterator first, last;
    first = HL[pos].begin();
    last = HL[pos].end();
    for (; first != last; ++first)
        if (visited[(*first).dest] == 0)
            DFS(L, (*first).dest, visited);
}

template <class T>
void Graph<T>::DFS(List<T> &L) const
{
    bool *visited = new bool[sizeV];
    for (int i = 0; i < sizeV; i++)
        visited[i] = 0;
    int i;
    for (i = 0; i < sizeV; i++)
        if (visited[i] == 0)
            DFS(L, i, visited);
}

template <class T>
void Graph<T>::DFS(List<T> &L, const T &v) const
{
    int pos = FindNode(v);
    if (pos == -1)
        return;
    bool *visited = new bool[sizeV];
    for (int i = 0; i < sizeV; i++)
        visited[i] = 0;
    DFS(L, pos, visited);
}

template <class T>
bool Graph<T>::Prim(const T &v, PathData E[], int ne) const
{
    int i, j, s, ns;
    PathData item;
    double cost;
    s = FindNode(v);
    if (s == -1)
        return 0;
    int id = 0;
    for (i = 0; i <= ne; i++)
        if (i != s)
        {
            item.start = s;
            item.dest = i;
            cost = GetCost(s, i);
            item.cost = (cost == 0 ? MAXCOST : cost);
            E[id++] = item;
        }
    int count = 0;
    BuildHeap(E, ne);
    for (i = 0; i < ne; i++)
    {
        if (E[0] < MAXCOST)
            count++;
        ns = E[0].dest;
        for (j = 1; j < ne - i; j++)
        {
            cost = GetCost(ns, E[j].dest);
            cost = (cost == 0 ? MAXCOST : cost);
            if (E[j] > cost)
            {
                E[j].cost = cost;
                E[j].start = ns;
            }
        }
        item = E[0];
        E[0] = E[ne - 1 - i];
        E[ne - 1 - i] = item;
        PercolateDown(E, 0, ne - 1 - i);
    }
    return count == ne ? 1 : 0;
}

template <class T>
bool Graph<T>::Kruskal(PathData E[], int ne) const
{
    Heap<PathData> H;
    int nv = ne + 1;
    int i, j, *DS = new int[nv];
    for (i = 0; i < nv; i++)
        DS[i] = -1;
    double cost;
    PathData e;
    for (i = 0; i < nv; i++)
        for (j = i + 1; j < nv; j++)
        {
            cost = GetCost(i, j);
            if (cost != 0)
            {
                e.start = i;
                e.dest = j;
                e.cost = cost;
                H.Insert(e);
            }
        }
    int id = 0;
    while (!H.Empty())
    {
        H.DeleteMin(e);
        i = e.start;
        while (DS[i] >= 0)
            i = DS[i];
        j = e.dest;
        while (DS[j] >= 0)
            j = DS[j];
        if (i != j)
        {
            if (i < j)
            {
                DS[i] += DS[j];
                DS[j] = i;
            }
            else
            {
                DS[j] += DS[i];
                DS[i] = j;
            }
            E[id++] = e;
        }
    }
    return id == ne ? 1 : 0;
}

template <class T>
bool Graph<T>::Dijkstra(const T &v, double D[], int P[], int nv) const
{
    int i, j, s, ns, ne = nv - 1;
    PathData item, *E = new PathData[ne];
    double cost;
    s = FindNode(v);
    if (s == -1)
        return 0;
    D[s] = 0;
    P[s] = -1;
    int id = 0;
    for (i = 0; i <= ne; i++)
        if (i != s)
        {
            item.start = s;
            item.dest = i;
            cost = GetCost(s, i);
            item.cost = (cost == 0 ? MAXCOST : cost);
            E[id++] = item;
            D[i] = item.cost;
            P[i] = (cost == 0 ? -1 : s);
        }
    int count = 0;
    BuildHeap(E, ne);
    for (i = 0; i < ne; i++)
    {
        if (E[0] < MAXCOST)
            count++;
        ns = E[0].dest;
        for (j = 1; j < ne - i; j++)
        {
            cost = GetCost(ns, E[j].dest);
            cost = (cost == 0 ? MAXCOST : cost);
            if (E[j] > E[0] + cost)
            {
                E[j].cost = E[0].cost + cost;
                E[j].start = ns;
                D[E[j].dest] = E[j].cost;
                P[E[j].dest] = ns;
            }
        }
        item = E[0];
        E[0] = E[ne - 1 - i];
        E[ne - 1 - i] = item;
        PercolateDown(E, 0, ne - 1 - i);
    }
    return count == ne ? 1 : 0;
}

template <class T>
double Graph<T>::MinPath(const T &sv, const T &dv) const
{
    int si = FindNode(sv), dj = FindNode(dv);
    if (si == -1 || dj == -1)
        return (-1);
    bool *visited = new bool[sizeV];
    for (int i = 0; i < sizeV; i++)
        visited[i] = 0;
    int id;
    double mincost, cost;
    Heap<PathData> PQ;
    PathData item;

    item.start = item.dest = FindNode(sv);
    item.cost = 0;
    PQ.Insert(item);
    id = FindNode(dv);

    while (!PQ.Empty())
    {
        PQ.DeleteMin(item);
        cout << item.start << ',' << item.dest << ',' << item.cost << endl;
        dj = item.dest;
        mincost = item.cost;
        if (dj == id)
            break;
        if (visited[dj] == 0)
        {
            visited[dj] = 1;
            si = dj;
            for (dj = 0; dj < sizeV; dj++)
            {
                cost = GetCost(si, dj);
                if (cost != 0 && visited[dj] == 0)
                {
                    item.start = si;
                    item.dest = dj;
                    item.cost = mincost + cost;
                    PQ.Insert(item);
                }
            }
        }
    }
    if (dj == id)
        return mincost;
    return -1;
}
template <class T>
void Graph<T>::AllPath(double *A[], int *P[], int nv) const
{
    int i, j, k;
    double cost;
    for (i = 0; i < nv; i++)
        for (j = 0; j < nv; j++)
        {
            if (i != j)
            {
                cost = GetCost(i, j);
                A[i][j] = (cost == 0 ? MAXCOST : cost);
            }
            else
                A[i][j] = 0;
            P[i][j] = (A[i][j] == MAXCOST ? -1 : i);
        }
    for (k = 0; k < nv; k++)
        for (i = 0; i < nv; i++)
            for (j = 0; j < nv; j++)
                if (A[i][k] + A[k][j] < A[i][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    P[i][j] = P[k][j];
                }
}

template <class T>
bool Graph<T>::TopSort(int *t, int nv) const
{
    int i, j, id, count = 0;
    int *ID = new int[nv];
    Queue<int> Q;
    for (i = 0; i < nv; i++)
    {
        ID[i] = InDegree(i);
        if (ID[i] == 0)
            Q.Push(i);
    }
    typename List<EdgeNode>::const_iterator first, last;
    id = 0;
    while (!Q.Empty())
    {
        i = Q.Pop();
        t[id++] = i;
        count++;
        first = HL[i].begin();
        last = HL[i].end();
        for (; first != last; ++first)
        {
            j = (*first).dest;
            ID[j]--;
            if (ID[j] == 0)
                Q.Push(j);
        }
    }
    delete[] ID;
    if (count == nv)
        return 1;
    return 0;
}

template <class T>
bool Graph<T>::TopSort(List<T> &L) const
{
    int *top = new int[sizeV];
    if (TopSort(top, sizeV))
    {
        for (int i = 0; i < sizeV; i++)
            L.Push_back(VA[top[i]]);
        delete[] top;
        return 1;
    }
    delete[] top;
    return 0;
}

template <class T>
void Graph<T>::CriticalPath(double VE[], double VL[], int nv) const
{
    int i, j, k;
    int *top = new int[nv];
    double min, max, temp;
    if (TopSort(top, nv))
    {
        for (int n = 0; n < nv; n++)
            cout << top[n] << ',';
        cout << endl;
        VE[top[0]] = 0;
        for (k = 1; k < nv; k++)
        {
            j = top[k];
            max = 0;
            for (i = 0; i < nv; i++)
            {
                temp = GetCost(i, j);
                if (temp != 0 && (VE[i] + temp) > max)
                    max = VE[i] + temp;
            }
            VE[j] = max;
        }
        VL[top[nv - 1]] = VE[top[nv - 1]];
        for (k = nv - 2; k > -1; k--)
        {
            i = top[k];
            min = MAXCOST;
            for (j = 0; j < nv; j++)
            {
                temp = GetCost(i, j);
                if (temp != 0 && (VL[j] - temp) < min)
                    min = VL[j] - temp;
            }
            VL[i] = min;
        }
    }
    delete[] top;
}

#endif
